/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年01月07日
*   描    述：
*
================================================================*/

/*
 * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0
 * 。请使用 原地 算法。
 *
 * 示例 1： 输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
 *   输出：[[1,0,1],[0,0,0],[1,0,1]]
 *
 * 示例 2：
 *   输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
 *   输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
 *
 * 提示：
 *   m == matrix.length
 *   n == matrix[0].length
 *   1 <= m, n <= 200
 *   -231 <= matrix[i][j] <= 231 - 1
 *
 *
 * 进阶：
 *   一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
 *   一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
 *   你能想出一个仅使用常量空间的解决方案吗？
 */

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void setZeroes(int **matrix, int matrixSize, int *matrixColSize) {
  int m = matrixSize, n = *matrixColSize;
  bool *xarray = (bool *)malloc(m * sizeof(bool));
  memset(xarray, 0, m * sizeof(bool));
  bool *yarray = (bool *)malloc(n * sizeof(bool));
  memset(yarray, 0, n * sizeof(bool));

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (matrix[i][j] == 0) {
        xarray[i] = true;
        yarray[j] = true;
      }
    }
  }

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (xarray[i] || yarray[j]) {
        matrix[i][j] = 0;
      }
    }
  }

  free(xarray);
  free(yarray);
}

int main() {
  int matrixData[][4] = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
  int matrixSize = sizeof(matrixData) / sizeof(matrixData[0]);
  int matrixColSize = 4;

  int *matrix[matrixSize];
  for (int i = 0; i < matrixSize; i++) {
    matrix[i] = matrixData[i];
  }

  setZeroes(matrix, matrixSize, &matrixColSize);

  printf("Modified Matrix:\n");
  for (int i = 0; i < matrixSize; i++) {
    for (int j = 0; j < matrixColSize; j++) {
      printf("%d ", matrix[i][j]);
    }
    printf("\n");
  }

  return 0;
}
